package com.mlamp.排序算法;


import java.util.Arrays;

public class 快速排序 {

    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        int[] ints1 = quickSort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints1));

        int[] inputs = new int[]{5, 1, 7, 3, 1, 6, 9, 4};
        quickSORT(inputs, 0, inputs.length - 1);
        System.out.println(Arrays.toString(inputs));

    }


    public static int[] quickSort1(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
        int smallIndex = partition1(array, start, end);
        if (smallIndex > start) quickSort(array, start, smallIndex - 1);
        if (smallIndex < end) quickSort(array, smallIndex + 1, end);
        return array;
    }


    public static int[] quickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start) quickSort(array, start, smallIndex - 1);
        if (smallIndex < end) quickSort(array, smallIndex + 1, end);
        return array;
    }


    public static int partition3(int[] array, int start, int end) {
        int pivotIndex = (int) (start + Math.random() * (end - start + 1));
        int smallIdx = start - 1;
        //swap pivotIndex and end
        int temp = array[end];
        array[end] = array[pivotIndex];
        array[pivotIndex] = temp;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIdx++;
                if (smallIdx < i) {
                    //swap the i with smallidx
                    int tmp = array[smallIdx];
                    array[smallIdx] = array[i];
                    array[i] = tmp;
                }
            }
        }
        return smallIdx;
    }


    private static int partition1(int[] array, int start, int end) {
        int pivotIndex = start + (int) (Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        int temp = array[end];
        array[end] = array[pivotIndex];
        array[pivotIndex] = temp;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (smallIndex < i) {
                    temp = array[smallIndex];
                    array[smallIndex] = array[i];
                    array[i] = temp;
                }
            }
        }
        return smallIndex;
    }

    private static int partition(int[] array, int start, int end) {
        int pivotIndex = start + (int) (Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        int temp = array[end];
        array[end] = array[pivotIndex];
        array[pivotIndex] = temp;
        //        //28, 54, 63, 45,  71, 78, 58
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (smallIndex < i) {
                    temp = array[smallIndex];
                    array[smallIndex] = array[i];
                    array[i] = temp;
                }
            }
        }
        return smallIndex;
    }


    public static void quickSORT(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) return;
        int left = leftIndex, right = rightIndex;
        int key = nums[left];
        while (left < right) {
            while (right > left && nums[right] >= key) {
                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] <= key) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        quickSORT(nums, leftIndex, left - 1);
        quickSORT(nums, right + 1, rightIndex);
    }

}
